1. Field of the Invention
The invention relates to computational architectures for parallel processing of signals and, more particularly, to massively parallel implementations of neural networks for path generation applications.
2. Description of Related Art
A number of practical problems in advanced technology require such a substantial amount of computations that real-time solutions are essentially unavailable from current technology. For example, one type of problem falling within this category relates to path planning in a multidimensional space. That is, in a large "problem space" (typically with several state variables) or "search space," it may be desired to search possible paths for a path having an optimal or "near optimal" performance measure through the space. The measure of performance is typically quantitatively expressed as a cost function associated with the selected path. In view of the relatively large search space, this type of path planning problem subjects computational resources to severe demands.
Solutions to problems such as path planning as described above are currently the subject of substantial research and development. In part, this research and development is directed to computer architectures for providing real time solutions to these problems. Although state-of-the-art digital computers are extremely powerful, such computers still exhibit certain limitations in problem solving. That is, many practical problems, such as real time path optimization, require such a substantial amount of computation that real time solutions were not earlier possible. Along with path optimization, pattern recognition problems are another category where computational requirements are substantially beyond state-of-the-art digital computers.
The development of real time solutions to problems such as path planning optimization and pattern recognition have led to substantial research and development associated with parallel processing of signals. For purposes of understanding the background of parallel computer structures, three configurations of parallel structures are described in Hwang and Briggs, Computer Architecture and Parallel Processing, McGraw-Hill 1984. These architectural configurations are typically characterized as pipeline computers, array processors and multiprocessor systems. In describing these types of architectural configurations, Hwang and Briggs also describe particular types of parallelism resulting from the configurations. For example, temporal parallelism results from pipeline computers as a result of the use of overlapped computations. Correspondingly, spatial parallelism results from multiple synchronized arithmetic logic units in array processors. Further, asynchronous parallelism is described within multiprocessor systems through the use of interactive processors having shared resources, such as memories, databases and the like.
With today's advanced state of the art in computer technology, parallel computers with 10.sup.5 to 10.sup.6 gates per chip facilitate the fabrication of massively parallel computers. Accordingly, a substantial amount of research has been directed to the understanding of the basic properties of highly parallel computation. For example, connectionist models (typically referred to as CM's) have resulted from the desire to understand computation in massively parallel architectures. In Fahlman and Hinton, "Connectionist Architectures for Artificial Intelligence," Computer, January 1987, the concept of research directed to the exploration of the use of massively parallel computer architectures is described as basically an attempt to avoid the conventional limitations of symbolic processing.
System response times for computers depend on the throughput, memory and interfacing capacities of the individual computer or computer network. In path planning applications, real time solutions are extremely difficult due to the massive computational throughput requirement associated with an extensive search space.
Extensive development has been performed with regard to parallelized versions of combinatorial search procedures. Other conventional search procedures, such as breadth-first, depth-first, alpha-beta, dynamic programming and the like, have been transformed into parallel versions. These parallelized search procedures are based on multiprocessor architectures comprising serial processors. Accordingly, this parallelizing has focused on data and control partitioning so as to address resource allocation of processors and memory only, rather than relatively unique parallel processing architectures.
As a result of the development associated with parallel processing, one type of technology which is considered to have a substantial potential with respect to such massively parallel architectures is neural networks. The development of neural network technology is often considered to have begun in 1943, and is described in McCulloch and Pitts, "A Logical Calculus of the Ideas Immanent in Nervous Activity," Bulletin of Mathematical Biophysics, Vol. 5, 1943, pp. 115-133. McCulloch and Pitts describe the use of the biological neuron as a computational model to compute boolean operations. Such a computing architecture is considered to be an alternative to the conventional Von Neumann architecture. A neural network is considered to be relatively distinct, in that the network can be programmed with data derived from its environment for purposes of adaptation instead of being conventionally programmed. Correspondingly, neural networks exhibit massive parallelism, with relatively high speed and inherent fault tolerance. Even animals with a relatively simple neural system structure can solve problems which would be difficult for solution by conventional digital computers.
Neural networks are essentially "motivated" by the biological neuron, an example of which is illustrated in FIG. 1. As shown in FIG. 1, a functional model of a simulated neuron comprises a series of synapses which act to provide outputs from other neurons and to provide inputs to the illustrated neuron. Inputs to the neuron from the synapses are typically characterized as dendrites. The "body" of the neuron, typically characterized as the soma, is functionally similar to a summer/threshold circuit. The output of the neuron, characterized as the axon, can be applied on axonal paths to the interconnection synapses.
Although neuronal computing elements may be relatively slow (on the order of 10.sup.-3 seconds), complex parallel connections of neuronal computing elements can result in relatively complex parallel processing having an overall "fast" throughput. Neurons with a computational speed of a few milliseconds can actually account for complex behavior in a few hundred milliseconds. Entire complex behaviors can be accomplished in a few hundred time steps of the computational system.
A physically realized neural network can comprise a highly parallel computational circuit having a series of amplifiers, with each of the amplifiers feeding back its output signal to itself and other amplifiers through a conductance T.sub.ij. In one type of embodiment of a neural network, the T.sub.ij conductances (where T.sub.ij denotes the conductance between the output of amplifier j and the input of amplifier i) and the associated connections can be characterized as a connection network having one output signal set and two input signal sets.
The output signal set is applied to the amplifier inputs, one of the input signal sets is derived from the amplifier outputs, and the other input signal set is responsive to input stimuli applied to the neural network. As is known in the art, the values of the T.sub.ij conductances can be defined so as to achieve predetermined results, such as attaining different specified output states of the amplifiers in response to different ranges of input stimuli. As also known in the art, an input interconnection network may be interposed between the input stimuli and the second set of inputs of the feedback network. This input interconnection network, comprising a feed-forward arrangement, converts the expected input signals to corresponding signals which drive the feedback network and amplifiers. The foregoing is merely one type of neural network, as described in Hopfield et al, U.S. Pat. No. 4,937,872 issued Jun. 26, 1990.
Neural networks exhibit various advantageous characteristics. Among these are the following:
1. Neural networks tend to be relatively resistant to hardware failures; PA1 2. Pattern recognition occurs in a parallel mode; PA1 3. Multiple layers in neural networks realize hierarchical data structures; PA1 4. Some neural network structures exhibit properties of adaptive biological learning; and PA1 5. Neural networks appear to be capable of capturing patterns in space, time, discrete and continuous representational models.
The connectionist model can be employed to describe a neural network. One of the fundamental concepts of connectionism as applied to neural networks is based on the premise that individual neurons do not transmit large amounts of symbolic information. Instead, a neural network provides computation by appropriate connections to relatively large numbers of similar computational elements. In a system employing connectionist parallel architecture, the "permanent" knowledge of the system is stored as patterns of connection-to-connection "strengths" among processing elements. In what is known as a "compact" connectionist model, the activity of a set of neurons tends to encode a concept group, instead of exactly one neuron accounting for any single individual concept. In what is known as a "diffuse" connectionist model, concepts are represented by a pattern of activity as a relatively larger set of neurons, which concurrently represent other concepts.
In further explanation, the connectionist model comprises a formalism of massively parallel models of computation. Such models are based upon information processing properties of neurons. As earlier mentioned, neurons are relatively slow as computing elements, but neuron networks have relatively complex parallel interconnections to other neurons. As also earlier mentioned, the processing characteristics of neurons can account for relatively complex behavior in a relatively few number of steps.
The contribution of the massive interconnection complexity can be characterized as a substrate for relatively more complex information processing capabilities. Accordingly, the connectionist model is based upon a theory that individual neurons do not exchange vast quantities of symbolic information, but instead perform computations by the complex interconnections between similar computationally simple units. Such interconnections allow for communication by means of spreading activation over weighted links among neurons.
For a connectionist model to be adaptable to physically realizable applications, the network of units requires a means for purposes of making decisions, or to perform some coherent action, as exemplified by animal and human behavior. Such a requirement implies that the networks must converge to stable states to effect decision making and coherent actions.
For purposes of providing additional background, the following paragraphs discuss various principles associated with particular search algorithms. Concepts associated with simulated annealing are described in Fahlman and Hinton, "Connectionist Architectures for Artificial Intelligence," Computer, January 1987. In this reference, Fahlman and Hinton describe the back propagation algorithm as a gradient descent search in a space of potential representational schemes.
For purposes of illustrating the "settling down" of a network during a back propagation search, it must be shown that a cost function exists which tends to decrease at each value change. In networks having symmetrically connected binary threshold units, a cost function typically characterized as the "energy" can be employed.
Each unit must determine the difference between the global energy of the network when the unit is disabled, and the global energy when the unit is enabled, given current states of other units. Such a difference is characterized as the "energy gap." If the energy gap is positive, the unit should be enabled or should remain enabled, so as to minimize the global energy. Otherwise, the unit should be disabled or should remain disabled.
A simulated annealing search, for purposes of escaping local minima, can be employed within an architecture which utilizes a particular type of network with hidden units. Simulated annealing escapes from high local minima by adding a random component to each unit's decision process. The gradient descent search step of simulated annealing is typically negative, but the step can be occasionally positive.
For purposes of a full understanding of the background of search algorithms, and although not necessarily required for an understanding of a processing structure in accordance with the invention, the following paragraphs describe concepts associated with dynamic programming. A more detailed analysis of the concepts associated with the same is set forth in Bellman, Dynamic Programming, Princeton University Press, 1957. In the aforedescribed reference, dynamic programming is introduced by describing a problem associated with multi-stage allocation processes. In such a process, the quantity x is expressed as two non-negative parts, y and x-y. In each stage of the process, the quantity y returns a value g(y) and the quantity x-y returns a value h(x-y). In accordance with the foregoing, total return for a single stage process is accomplished by maximizing the following function: ##EQU1## The "price" to obtain the value g(x) is a reduction of y to ay. Correspondingly, to obtain the value h(x-y) the value x-y is reduced to b(x-y), with a greater than or equal to 0 and b less than 1. The function f.sub.n (x) is the "maximum" return obtained from an n-stage process starting with the initial quantity x, for x greater than or equal to 0. This function can be described as follows: ##EQU2## For this first stage, namely f.sub.1 (x), the function can be defined as follows: ##EQU3## For n stages, the function can be defined as a recursive function in accordance with the following: ##EQU4##
Dynamic programming processes include several characteristic features. Specifically, the physical system for such a process is represented at any stage of the process by a relatively small set of parameters characterized as "state variables." At each stage of the process, a choice can be made from a number of possible decisions. The effects of the decision chosen at each stage of the process is a transformation of the state variables. Further, the past "history" of the system is unimportant with respect to determination of future actions. The purpose of the dynamic programming process is to maximize or minimize some "function" of the state variables.
For purposes of further description of concepts associated with dynamic programming, several known definitions are typically utilized. More specifically, a "policy" is typically defined as any rule for making decisions which result in allowable sequences of decisions. An "optimal" policy is typically characterized as the policy which maximizes or minimizes the pre-assigned function of the final state variables. In accordance with what is typically characterized as the "principle of optimality," an optimal policy comprises the property that regardless of the initial state and initial decision, remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.
Another conceptual arrangement is described in Dreyfus and Law, The Art and Theory of Dynamic Programming, Academic Press 1977. In this arrangement, the principle of optimality is defined as the best path from A to B having the property that, whatever is the initial decision at A, the remaining path to B, starting from the next point after A, must be the best path from that point to B. Further, the assignment of values to the various "subproblems" is characterized as the "optimal value function." In addition, the function which associates the best first decision with each subprogram is characterized as the "optimal policy function."
Returning again to neural network architecture, with the background associated with search algorithms as described in the foregoing paragraphs, computational methods based on neural networks are being developed for complex problems associated with learning, pattern classification/recognition and path planning.
Developments in artificial neural network approaches to constrained optimization problems, coupled with advances in integrated circuit technology, have resulted in advancement of developments associated with enhancing real-time control, decision-making and parameter compensation processes. Neural networks have been used in solving optimization problems expressed in the form of linear programming models, and functional optimization in the form of iterated descent. Neural computation can be characterized as being analogous to searching for a path which extends through a "valley" within an energy contour. Neural networks can further be characterized as computing by defining a computational energy function which has resulted from the optimization function.
Various known developmental projects have involved neural network models for purposes of solving constrained optimization problems. The results of these developments appear to indicate that properly designed neural networks can provide relatively rapid computations, with relatively "good" optima. Processing elements utilized in several of these developmental circuits or models comprise relatively simple analog neurons which are conducive to ultra-dense VLSI implementations. Detailed neural circuits for solving small linear programming problems constructed from non-linear operational amplifiers have also been described in the art.
The data elements of the mathematical model can be composed of vectors and matrices. The computations involve matrix-vector products and integrations repeated over a set of data. Such data-parallel computations can be executed relatively efficiently on a massively parallel machine. For purposes of achieving such speeds, a relatively good data-partitioning scheme is required, as well as a reduction of the communications.
Although not obvious from the prior art, the neural network architecture associated with the invention involves electric field theory. Accordingly, the following paragraphs briefly describe background principles of electric field theory pertinent to the invention.
The divergence of the current density j is defined as the charge (p) rate of change in accordance with the following: ##EQU5## In the steady state condition, no charge distribution changes occur, the charge rate of change is zero and, accordingly, the divergence of the current density j is zero.
The current density is defined in terms of the electric field E and the conductivity .sigma. in accordance with the following: EQU j=.sigma.E (Equation 6)
In the steady state condition, with the divergence of the current density being zero, Equation 5 can be written as follows: EQU .gradient..multidot.(.sigma.E)=0 (Equation 7)
Using vector identity principles, Equation 7 can be written as: EQU .gradient..sigma..multidot.E+.sigma..gradient..multidot.E=0 (Equation 8)
The electric field E can also be defined as the negative gradient of the potential field .phi. as follows: EQU E=-.gradient..phi. (Equation 9 )
By substituting the negative gradient of the potential field .phi. in the vector identity principle Equation 8, Equation 8 can now be written as follows: EQU .gradient..sigma..multidot.(-.gradient..phi.)+.sigma..gradient..multidot.(- .gradient..phi.)=0 (Equation 10)
By dividing Equation 10 by the term -.sigma., the following expression is obtained for the electric field potential of a nonuniform conductive media: ##EQU6##
With the gradient and divergence operators of Equation 11 expanded in two dimensions, the following second order partial differential equation is obtained: ##EQU7## With x and y representing the two dimensions, Equation 12 can be defined in subscript notation as follows: ##EQU8##
As earlier described, various network architectures have been developed for the general path planning problem and for the specific problem of finding optimal or near optimal paths among a multiple of paths. Although development is relatively extensive, the known network architectures directed to the path planning problem suffer from several disadvantages.
The Hopfield network has the advantage that its implementation as an analog circuit is relatively straight forward. However, one drawback to the Hopfield network is that the high gain limit is relatively difficult to physically implement. Another drawback associated with the network is that a globally optimal solution can only be obtained when the conductances are infinite, as shown in Maa and Shonblatt, "Stability of Linear Programming Neural Networks for Problems with Hybercube Flexible Region," Proceedings of the 1990 International Joint Conference on Neural Networks, June 1990.
Another disadvantage is associated with the potential difficulty in defining an appropriate energy function for the Hopfield network, where the energy function corresponds to the desired optimization problem. A further disadvantage is that some convergence states, comprising local minima, may represent infeasible solutions to the optimization problem. Still further, the network is highly sensitive to parameterization and initial conditions. These and other concepts associated with the Hopfield network are described in Wilson and Pauley, "On the Stability of the Travelling Salesman Problem Algorithm of Hopfield and Tank," Biological Cybernetics, Vol. 58, 1988, pgs. 63-70; Kahng, "Travelling Salesman Heuristics and Embedding Dimension in the Hopfield Model," IEEE International Conference on Neural Networks, 1989, Vol. 1, pgs. 513-520.